#include <iostream>
#include <stdlib.h> // srand rand
#include <algorithm> // max

using namespace std;

template <class T>
class Node{
public:
    Node<T> *left, *right;
    T val;

    explicit Node( const T &_in, Node<T> *L = NULL, Node<T> *R = NULL ) :
                    val( _in ), left( L ), right( R ) { ; }
    
    Node( const Node<T> &n )
    {
        val = n.val;
        left = n.left;
        right = n.right;
    }
    
    ~Node(){ ; }    
    
    friend ostream & operator << ( ostream &out, const Node<T> &n )
    {
        out << n.val <<" ,L: " << (bool)n.left << " ,R: " << (bool)n.right;
        return out;
    }
};

template< class T >
class BST{
private:
    class ParentNode{
    public:
        Node<T> *parent;
        int tag; // 0: invalid; 1:left; 2:right; 3:root
        
        ParentNode():parent(NULL), tag(0){;}
        explicit ParentNode( Node<T> *p, int t=0 ) : parent(p), tag(t) {;}
        ~ParentNode(){ ; }        
        
        Node<T> * childPtr()const
        {
            if( tag==0 )
                return NULL;
            if( tag==1 )
                return parent->left;
            if( tag==2 )
                return parent->right;
            if( tag==3 )
                return parent;
        }
    };
private:
    Node<T> * root;
    long count;
    
    // for recursive clean 
    void clean( Node<T> **_root )
    {
        // check if tree is empty
        if( _root==NULL ) return;
        
        // clean the children
        // this block codes have be executed before deletion recursively
        if( (*_root)->left )
        {
            clean( &((*_root)->left) );
        }   
        if( (*_root)->right )
        {
            clean( &((*_root)->right) );    
        }
                
        // delete the node without any child
        if( (*_root)->left==NULL && (*_root)->right==NULL )
        {
            delete *_root;
            *_root = NULL;
            count--;
            return;
        }        
    }      
    
    // for recursive insert; since root pointer will be changed,
    // the input paramter for root should be pointer's pointer
    void insert( Node<T> **_root, const T & _val )
    {
        if( *_root==NULL )
        {     
            *_root = new Node<T>(_val);
            count++;
        }else{
            if( _val <= (*_root)->val )
            {            
                insert( &((*_root)->left), _val );
            }else{
                insert( &((*_root)->right), _val );
            }
        }        
    }        
    
    // get height of node
    int getHeight( Node<T> *currNode )
    {
        if( currNode==NULL ) return 0;
        return 1 + max( getHeight( currNode->left ),
                        getHeight( currNode->right )        
                      );    
    }
    
    // for recursive preorder traverse
    void preorder( Node<T> const * const _root )
    {
        if ( _root==NULL ) return;
        cout << "-> " << *_root << endl;
        preorder( _root->left );
        preorder( _root->right );
    }
    void inorder( Node<T> const * const _root )
    {
        if ( _root==NULL ) return;
        inorder( _root->left );    
        cout << "-> " << *_root << endl;
        inorder( _root->right );
    }
    void postorder( Node<T> const * const _root )
    {
        if ( _root==NULL ) return;
        postorder( _root->left );
        postorder( _root->right );
        cout << "-> " << *_root << endl;        
    }    

    // O( log(n) )
    Node<T> * find( Node<T> * const _root, const T &_val )
    {
        if( _root==NULL ) return NULL;

        if( _val == _root->val )
        {
            return _root;
        }
        if( _val < _root->val )
            return find( _root->left, _val );
        else
            return find( _root->right, _val );                        
    }
        

    // find a node's parent and return the connected slot tag number: 
    // root = 0, left = -1 and right = 1
    ParentNode findParent( const T &_val )
    {
        ParentNode result;

        // if tree is empty, return a NULL parent node
        if( root==NULL ) return result; 
        
        if( _val==root->val )
        {
            result.parent = root;
            result.tag = 3;         
            return result;
        }
        
        Node<T> *next = root;
        while(next)
        {        
            if( _val < next->val )
            {
                if( next->left==NULL )
                    break;
                if( _val == next->left->val )
                {
                    result.parent = next;
                    result.tag = 1;
                    break;
                    //return result;
                }else{
                    next = next->left; // advance
                }                
            }else{
                if( next->right==NULL )
                    break;
                if( _val == next->right->val )
                {
                    result.parent = next;
                    result.tag = 2;
                    break;
                    //return result;
                }else{
                    next = next->right;
                }
            }
        }
        //cout << "tag: " << result.tag << endl;       
        return result;
    }    
    
                
public:
    BST() : root(NULL), count(0){ ; }
    ~BST()
    { 
        //clean(); 
    }
    
    // get total number of nodes
    long getSize()const{ return count; }
    
    // get node height
    int getHeight( const T &_val ){ getHeight( find( _val) ); }
    
    // balanced tree O(log(n)), otherwise O(n)
    Node<T> * find( const T &_val ){ find( root, _val ); }
    
    void preorder(){ preorder( root ); }   
    void inorder(){ inorder( root ); }   
    void postorder(){ postorder( root ); }   
    
    
    // find the minimum node along left branch
    Node<T> * minNode( Node<T> *_root )
    {
        if( _root==NULL ) return NULL;
        
        while( _root )
        {
            if( _root->left )
                _root = _root->left;
            else
                break;
        }
        return _root;
    }
    
        // find the maximum node along right branch
    Node<T> * maxNode( Node<T> *_root )
    {
        if( _root==NULL ) return NULL;
        
        while( _root )
        {
            if( _root->right )
                _root = _root->right;
            else
                break;
        }
        return _root;
    }
            
    // O(log(n))
    void insert( const T &_val ){insert( &root, _val );}                
        
    // O(log(n))
    bool delNode( const T &_val )
    {
        ParentNode pNode = findParent( _val );
        
        // if the required node does not exist, return false
        if( pNode.tag==0 ) return false;
        
        Node<T> *delNode = pNode.childPtr(); // the required node
        
        // no child
        if( !(delNode->left) && !(delNode->right) )
        {
            // update parent node pointers
            if( pNode.tag==3 )             // root
                root = NULL;
    
            else if( pNode.tag==1 )        // parent left
                pNode.parent->left = NULL;
                
            else                           // parent right
                pNode.parent->right = NULL;                
            
            delete delNode; // delete required node
        }
        
        // 1 child
        int slotST = bool(delNode->left) + bool(delNode->right);
        if( slotST<2 && slotST )
        {
            // update parent node's pointers
            if( pNode.tag==3 )                            // root
                if( delNode->left )
                    root = delNode->left;
                else
                    root = delNode->right;
                        
            else if( pNode.tag==1 )                       // parent left
                if( delNode->left )
                    pNode.parent->left = delNode->left;
                else
                    pNode.parent->left = delNode->right;
                                
            else                                          // parent right
                if( delNode->left )
                    pNode.parent->right = delNode->left;
                else
                    pNode.parent->right = delNode->right;
                           
            delete delNode;
        }        
        
        // 2 children
        if( delNode->left && delNode->right )
        {
            // find the min value node from the right branch of target node
            Node<T> *minN = minNode( delNode->right );
            
            // find the min node's parent,
            // this step has to be execute before changing the removed node's value
            ParentNode minNparent = findParent( minN->val ); 
                        
            delNode->val = minN->val; // upate required node's value with this min value                                                                                                
            
            // update parent node's left pointer
            // in this case, the removed node is always connected with its parent's left slot
            if( minNparent.tag==1 )
                if( minN->left )
                    minNparent.parent->left = minN->left;
                else
                    minNparent.parent->left = minN->right;
                    
            if( minNparent.tag==2 )
                if( minN->left )
                    minNparent.parent->right = minN->left;
                else
                    minNparent.parent->right = minN->right;

            delete minN;
        }
        
        count--;
        return true;        
    }
    
    // clean entire tree data
    void clean(){ clean( &root ); }
};

int main()
{
    srand( 1024787989 ); // initialize rand seed               
    
    int num = 10;
    
    BST<int> bst;
    
    /*
    bst.insert( 100 );
    bst.insert( 50 );    
    bst.insert( 150 );
    bst.insert( 25 );    
    bst.insert( 75 );
    bst.insert( 125 );    
    bst.insert( 175 );    
    bst.insert( 110 ); 
    */
    
   
    cout << "insert int: "<< endl;
    for(int i=0; i<num; i++)
    {
        int tmp = rand()%num;
        tmp = i;
        bst.insert( tmp );
        cout << tmp <<","; 
    } 
    cout << endl;   
    bst.preorder();
    
    //bst.clean();
    cout << "bst size after clean: " << bst.getSize() << endl;
    
    bst.preorder();
    cout << endl << endl;           
        
    cout << "remove int: "<< endl;
    for(int i=0; i<num; i++)
    {        
        bst.delNode( i );
        cout << "remove "<< i << ", current number: " << bst.getSize() << endl;
        bst.preorder();
        cout << endl;
    } 
    cout << endl;       
    

    
    /*      
    cout << "test preorder for " << bst.getSize() << " nodes" << endl;
    bst.preorder();   
    cout << "test inorder for " << bst.getSize() << " nodes" << endl;
    bst.inorder();    
    cout << "test postorder for " << bst.getSize() << " nodes" << endl;
    bst.postorder();    
    */

    // bst.findParent( 75 );    
    // exit(0);  
    
    /*
    int target = 110;
    Node<int> *nn = bst.find( target );
    if (nn)
        cout << "find "<< target <<": " << *nn << endl;
        cout << target <<" ,height: " << bst.getHeight( target ) << endl;

    cout <<"minNode: " << *( bst.minNode( bst.find(75) ) ) << endl;
    cout <<"maxNode: " << *( bst.maxNode( bst.find(150) ) ) << endl;  
    */
    bst.inorder();
        
    bool st = bst.delNode( 50 );
    cout <<"del 50 st: "<< st << endl;    
    bst.inorder();

    st = bst.delNode( 25 );
    cout <<"del 25 st: "<< st  << endl;    
    bst.inorder();
    
    st = bst.delNode( 110 );    
    cout <<"del 110 st: " << st << endl;    
    bst.inorder();    

    st = bst.delNode( 125 );
    cout <<"del 125 st: " << st << endl;    
    bst.inorder();     
    
    st = bst.delNode( 100 );
    cout <<"del 100 st: " << st << endl;    
    bst.inorder(); 

    st = bst.delNode( 150 );
    cout <<"del 150 st: " << st << endl;    
    bst.inorder(); 
    
    st = bst.delNode( 175 );
    cout <<"del 175 st: " << st << endl;    
    bst.inorder();   
    
    st = bst.delNode( 75 );
    cout <<"del 75 st: " << st << endl;    
    bst.inorder();                   
}